The present invention relates to a technology of selecting a replace target way in a storage device having N-pieces of ways in a set associative system.
In the storage device having the N-pieces of ways in the set associative system, when registering new pieces of information, if storage areas of the storage device have already been all used with no registerable space left, it is required that some pieces of information to be deleted from the storage device be selected from the stored information and be replaced with the new pieces of registration information. A selection method thereof may be an LRU (Least Recently Used) algorithm for preferentially deleting the information that has not been used recently.
It needs, however, a good deal of cost to execute the LRU algorithm. The number of bits required at the minimum for executing the LRU algorithm is C(n,2)=n!/(r!(n−2)!) in the N-way device. For example, the device having the 4-ways needs 6-bit flags at the minimum, and these flags for the number of pipeline stages are sent round within the device. The device begins to work at a 6-fold cost, and therefore it follows that the cost becomes increasingly large with an increased number of pipeline stages. Other than the LRU, there are methods by which the flags indicating the replacement are set per way, however, those methods proposed so far are designed for 2 ways and unable to be applied to 3 or more ways, and hence a new technique needs to be developed.
It is an object of the present invention to provide a technology capable of selecting a way including an entry in which registration and replacement are conducted in a storage device having N-pieces of ways in a set associative system at a cost that is by far lower than by an LRU algorithm while exhibiting a performance approximate to the LRU.